6426. Сломать тюрьму

Миссия Джона состоит в том, чтобы вытащить двух человек из тюрьмы. Тюрьма представляет собой одноэтажное здание. Джон сумел достать подробный план этажа с указанием всех стен и дверей. Он также знает расположение двух людей, которых должен освободить. Тюремные охранники не проблема – он спланировал диверсию, в результате которой они покинут здание практически незаметно.

Двери являются его главной проблемой. Все двери, как правило, удаленно открываются из диспетчерской, однако Джон может открыть их с помощью других средств. После того как ему удалось открыть дверь, она остается открытой. Тем не менее открытие двери занимает много времени. Поэтому он хочет свести к минимуму количество дверей, которое он должен открыть. Сможете ли Вы помочь Джону спланировать оптимальный маршрут, по которому он сможет добраться до двух заключенных?

Вход. Первая строка содержит количество тестов, не более 100. Первая строка каждого теста содержит два числа n и m (2 ≤ n, m ≤ 100) – ширину и высоту карты. Следующие n строк по m символов описывают здание тюрьмы:

· ‘.’ пустое место.

· ‘*’ непроницаемая стена.

· ‘#’ дверь.

· ‘$’ один из двух людей которых следует освободить.

Джон может свободно перемещаться по внешней стороне здания. Карта содержит ровно два человека. До каждого человека внутри тюрьмы существует путь из внешней стороны.

Выход. Для каждого теста вывести в отдельной строке наименьшее количество дверей, которое Джон должен открыть для освобождения обоих узников.

Пример входа	Пример выхода
3 5 9 ****#**** *..#.#..* ****.**** *$#.#.#$* ********* 5 11 *#********* *$*...*...* *$*.*.*.*.* *...*...*.* *********.* 9 9 *#**#**#* *#**#**#* *#**#**#* *#**.**#* *#*#.#*#* *$##*##$* *#*****#* *.#.#.#.* *********	4 0 9

РЕШЕНИЕ

поиск в ширину

Анализ алгоритма

Прочитаем карту n * m в двумерный символьный массив так чтобы левый верхний угол карты находился в позиции (1, 1). Строки 0 и n + 1, а также столбцы 0 и m + 1 заполним символами ‘.’ (пустое место).

Каждую ячейку массива трактуем как вершину графа. Из каждой вершины можно передвигаться в четырех направлениях (вверх, вниз, вправо, влево). Передвигаться в клетку с символом ‘*’ запрещено (непроницаемая стена). Разрешенные передвижения – это ребра графа. Положим веса ребер равными нулю кроме тех, которые идут в ячейку ‘#’ (дверь). Ребрам, идущим в дверь, положим вес равный 1. Таким образом нами построен 0 – 1 граф.

Запустим три поиска в ширину на 0 – 1 графе: из вершин (0, 0), (a₁, b₁) и (a₂, b₂), где (a₁, b₁) и (a₂, b₂) – координаты заключенных. Результатом поиска в ширину будут соответственно три массива a, b, c. Например, a[i][j] хранит кратчайшее расстояние (наименьшее количество дверей которое следует открыть) от (0, 0) до (i, j).

Имеется два варианта освобождения узников:

· добраться из (0, 0) в (a₁, b₁), вернуться назад в (0, 0) и опять пойти из (0, 0) в (a₂, b₂). Число открытых дверей будет равно b[0][0] + c[0][0].

· пойти из (0, 0) в некоторую позицию (i, j) в которой находится дверь, затем пойти из (i, j) в (a₁, b₁), вернуться в (i, j) и снова пойти из (i, j) в (a₂, b₂). Число открытых дверей равно a[i][j] + b[i][j] + c[i][j] – 2. Каждое слагаемое учитывает открытие двери в ячейке (i, j). Однако дверь следует открывать не 3, а 1 раз. Поэтому из общей суммы следует вычесть 2. Перебираем все двери (i, j) и находим минимум среди значений a[i][j] + b[i][j] + c[i][j] – 2.

Реализация алгоритма

Объявим константы и тип матрица matrix. Входную карту храним в массиве g.

#define INF 0x3F3F3F3F

#define MAX 110

string g[MAX];

typedef vector<vector<int> > matrix;

matrix a, b, c;

Функция CanGo проверяет, не вышла ли точка с координатами (x, y) за границы сетки. В позиции (x, y) также не должна находиться непроницаемая стена (символ ‘*’).

int CanGo(int x, int y)

{

return (x >= 0) && (x <= n + 1) &&

(y >= 0) && (y <= m + 1) && g[x][y] != '*';

}

Функция bfs реализует поиск в ширину из точки (sx, sy). Возвращает двумерный массив, который в позиции (i, j) содержит наименьшее количество дверей которое следует открыть чтобы попасть из (sx, sy) в (i, j).

matrix bfs(int sx, int sy)

{

matrix dist(n + 2, vector<int>(m + 2, INF));

dist[sx][sy] = 0;

Инициализируем очередь. Заносим в нее стартовую вершину – пару (sx, sy).

deque<pair<int, int> > q;

q.push_back(make_pair(sx, sy));

Инициализируем массивы dx и dy. Пара (dx[i], dy[i]) содержит направление, в котором разрешено передвигаться по комнатам тюрьмы.

int dx[] = { 0, 0, -1, 1 };

int dy[] = { -1, 1, 0, 0 };

Основной цикл поиск в ширину.

while (!q.empty())

{

Извлекаем координаты (x, y) вершины из головы очереди.

int x = q.front().first;

int y = q.front().second;

q.pop_front();

Перебираем 4 ребра – направления, куда можно попасть из (x, y). Из точки (x, y) имеется ребро в (x + dx[i], y + dy[i]).

for (int i = 0; i < 4; i++)

{

int xx = x + dx[i];

int yy = y + dy[i];

if (!CanGo(xx, yy)) continue;

Если ребро идет в дверь, то его вес равен 1. Иначе вес ребра равен 0.

int w = (g[xx][yy] == '#');

Если ребро (x, y) – (xx, yy) релаксирует, то пересчитываем кратчайшее расстояние dist[xx][yy] и кладем вершину (xx, yy) или в начало или в конец очереди в зависимости от веса ребра.

if (dist[xx][yy] > dist[x][y] + w)

{

dist[xx][yy] = dist[x][y] + w;

if (w == 1)

q.push_back(make_pair(xx, yy));

else

q.push_front(make_pair(xx, yy));

}

}

}

return dist;

}

Основная часть программы. Читаем входные данные.

cin >> tests;

while (tests--)

{

Карта расположена в подмассиве [1 .. n] * [1 .. m].

cin >> n >> m;

Читаем карту тюрьмы. Строки 0 и n + 1, а также столбцы 0 и m + 1 заполним символами ‘.’ (пустое место).

g[0].resize(m + 1, '.');

a1 = -1;

for (i = 1; i <= n; i++)

{

cin >> g[i];

g[i] = " " + g[i] + " ";

for (j = 1; j <= m; j++)

Позиции заключенных читаем в (a₁, b₁) и (a₂, b₂).

if (g[i][j] == '$')

{

if (a1 == -1)

{

a1 = i; b1 = j;

}

else

{

a2 = i; b2 = j;

}

Символ ‘$’ меняем на ‘.’.

g[i][j] = '.';

}

}

g[n + 1].resize(m + 1, '.');

Запускаем поиск в ширину из позиций (0, 0), (a₁, b₁) и (a₂, b₂). Матрицы a, b и c содержат соответственно информацию о кратчайших расстояниях.

a = bfs(0, 0);

b = bfs(a1, b1);

c = bfs(a2, b2);

Вычисляем наименьшее количество дверей res, которое Джон должен открыть для освобождения обоих узников. Инициализируем res значением b[0][0] + c[0][0], когда каждого узника выводим независимо друг от друга.

int res = b[0][0] + c[0][0];

Проходим по всем ячейкам тюрьмы, находим двери.

for (i = 1; i <= n; i++)

for (j = 1; j <= m; j++)

Среди всех позиций дверей (i, j) ищем наименьшее значение ответа.

if (g[i][j] == '#')

res = min(res, a[i][j] + b[i][j] + c[i][j] - 2);

Выводим ответ.

cout << res << endl;

}